package _11_整理题目._3_字符串_递归_dfs_bfs_双指针._子串子序列_最值;

import org.junit.Test;

/**
 * https://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af?tpId=117&&tqId=37789&rp=1&ru=/activity/oj&qru=/ta/job-code-high/question-ranking
 *
 * 对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
 * 给定字符串A以及它的长度n，请返回最长回文子串的长度。
 *
 * 整体思路：
 *      回文结构：如果 s[i,j] 是回文子串，那么 s[i+1,j-1] 也是回文子串
 *      动态规划中 dp[i][j]=true 表示 s 从下标 i 到 j 的字符串为回文结构
 *      所以需要做两件事，s[i]~s[j] 是不是回文串，是的话，需要更新要返回的结果
 * 动态规划具体步骤：
 *      1、定义 dp 含义和长度：
 *              dp[i][j]=true 的含义：表示 s 从下标 i 到 j 的字符串为回文结构
 *          new dp[n][n]，n = s.length()
 *      2、定义边界值：
 *              dp[0][0] 表示 s[0] ，是回文，所以 = true
 *              dp[i][i] 表示 s[i] ，是回文，所以 = true
 *              dp[i][j] 当 i>j 时，没有意义，不用存储
 *              dp[i][j] 当 i<j 时，表示 s[i][j]，使用转移方程
 *      3、定义转移方程：
 *              dp[i][i+1] = true   if(s[i] == s[i+1])
 *              dp[i][j] = true     if(s[i] == s[j] && dp[i+1][j-1]==true)
 *      需要使用 位移 l 表示 从 i 往后的移位
 */

public class _031_最长回文子串 {
	public int longestPalindrome(String A, int n) {
		boolean[][] dp = new boolean[n][n];
		String maxString = "";
		for (int l = 0; l < n; l++) {
			for (int i = 0; i < n; i++) {
				int j = i + l;
				if (j >= n) break;

				if (l == 0) {
					dp[i][j] = true;
				} else if (l == 1) {
					dp[i][j] = A.charAt(i)==A.charAt(j);
				} else {
					dp[i][j] = A.charAt(i)==A.charAt(j) && dp[i+1][j-1];
				}
				
				if(dp[i][j] && j-i+1 > maxString.length()) {
					maxString = A.substring(i, j+1);
				}
			}
		}
		return maxString.length();
	}
	
	@Test
	public void main() {
		String s = "baabccc";
		assert longestPalindrome(s, 7) == 4;
	}
}
